/**
 * 1802. 有界数组中指定下标处的最大值
 * @param {number} n
 * @param {number} index
 * @param {number} maxSum
 * @return {number}
 */
// 贪心 + 二分
var maxValue = function (n, index, maxSum) {
	let left = 1,
		right = maxSum

	while (left < right) {
		const mid = Math.floor((left + right + 1) / 2)
		if (valid(mid, n, index, maxSum)) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}
const valid = (mid, n, index, maxSum) => {
	const left = index
	const right = n - index - 1
	return mid + cal(mid, left) + cal(mid, right) <= maxSum
}
const cal = (big, length) => {
	if (length + 1 < big) {
		const small = big - length
		return Math.floor(((big - 1 + small) * length) / 2)
	} else {
		const ones = length - (big - 1)
		return Math.floor((big * (big - 1)) / 2) + ones
	}
}
const res = maxValue(4, 0, 4)
console.log('maxValue :>>', res)
